Search Results

Documents authored by Håstad, Johan

Found 2 Possible Name Variants:

Hastad, Johan

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.24
Bounded Independence vs. Moduli

Authors: Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0,1}^n that is supported on the set S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer. We show that Omega(n/m^2 log m) <= k <= 2n/m + 2. For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over S_m. For any fixed odd m there is k \ge (1 - Omega(1))n such that any k-wise uniform distribution lands in S_m with probability exponentially close to |S_m|/2^n; and this result is false for any even m.
Cite as

Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded Independence vs. Moduli. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 24:1-24:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boppana_et_al:LIPIcs.APPROX-RANDOM.2016.24,
  author =	{Boppana, Ravi and H\r{a}stad, Johan and Lee, Chin Ho and Viola, Emanuele},
  title =	{{Bounded Independence vs. Moduli}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{24:1--24:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.24},
  URN =		{urn:nbn:de:0030-drops-66475},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.24},
  annote =	{Keywords: Bounded independence, Modulus}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.341
Improved NP-Inapproximability for 2-Variable Linear Equations

Authors: Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.
Cite as

Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright. Improved NP-Inapproximability for 2-Variable Linear Equations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 341-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hastad_et_al:LIPIcs.APPROX-RANDOM.2015.341,
  author =	{H\r{a}stad, Johan and Huang, Sangxia and Manokaran, Rajsekar and O’Donnell, Ryan and Wright, John},
  title =	{{Improved NP-Inapproximability for 2-Variable Linear Equations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{341--360},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.341},
  URN =		{urn:nbn:de:0030-drops-53112},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.341},
  annote =	{Keywords: approximability, unique games, linear equation, gadget, linear programming}
}
Document
DOI: 10.4230/DagRep.2.11.1
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)

Authors: Johan Hastad, Andrei Krokhin, and Dániel Marx

Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)

Abstract
During the past two decades, an impressive array of diverse methods from several different mathematical fields, including algebra, logic, analysis, probability theory, graph theory, and combinatorics, have been used to analyze both the computational complexity and approximabilty of algorithmic tasks related to the constraint satisfaction problem (CSP), as well as the applicability/limitations of algorithmic techniques. The Dagstuhl Seminar 12451 ``The Constraint Satisfaction Problem: Complexity and Approximability'' was aimed at bringing together researchers using all the different techniques in the study of the CSP, so that they can share their insights. This report documents the material presented during the course of the seminar.
Cite as

Johan Hastad, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). In Dagstuhl Reports, Volume 2, Issue 11, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{hastad_et_al:DagRep.2.11.1,
  author =	{Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.11.1},
  URN =		{urn:nbn:de:0030-drops-39764},
  doi =		{10.4230/DagRep.2.11.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjceture; Fixed-parameter tractability; Descriptive complexity; niversal algebra; Logic; Decomposition methods}
}
Document
DOI: 10.4230/DagSemRep.338
Complexity of Boolean Functions (Dagstuhl Seminar 02121)

Authors: Johan Hastad, Matthias Krause, David A. M. Barrington, and Rüdiger Reischuk

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Johan Hastad, Matthias Krause, David A. M. Barrington, and Rüdiger Reischuk. Complexity of Boolean Functions (Dagstuhl Seminar 02121). Dagstuhl Seminar Report 338, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{hastad_et_al:DagSemRep.338,
  author =	{Hastad, Johan and Krause, Matthias and Barrington, David A. M. and Reischuk, R\"{u}diger},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 02121)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{338},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.338},
  URN =		{urn:nbn:de:0030-drops-152207},
  doi =		{10.4230/DagSemRep.338},
}

Håstad, Johan

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.24
Bounded Independence vs. Moduli

Authors: Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0,1}^n that is supported on the set S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer. We show that Omega(n/m^2 log m) <= k <= 2n/m + 2. For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over S_m. For any fixed odd m there is k \ge (1 - Omega(1))n such that any k-wise uniform distribution lands in S_m with probability exponentially close to |S_m|/2^n; and this result is false for any even m.
Cite as

Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded Independence vs. Moduli. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 24:1-24:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boppana_et_al:LIPIcs.APPROX-RANDOM.2016.24,
  author =	{Boppana, Ravi and H\r{a}stad, Johan and Lee, Chin Ho and Viola, Emanuele},
  title =	{{Bounded Independence vs. Moduli}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{24:1--24:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.24},
  URN =		{urn:nbn:de:0030-drops-66475},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.24},
  annote =	{Keywords: Bounded independence, Modulus}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.341
Improved NP-Inapproximability for 2-Variable Linear Equations

Authors: Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.
Cite as

Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright. Improved NP-Inapproximability for 2-Variable Linear Equations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 341-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hastad_et_al:LIPIcs.APPROX-RANDOM.2015.341,
  author =	{H\r{a}stad, Johan and Huang, Sangxia and Manokaran, Rajsekar and O’Donnell, Ryan and Wright, John},
  title =	{{Improved NP-Inapproximability for 2-Variable Linear Equations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{341--360},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.341},
  URN =		{urn:nbn:de:0030-drops-53112},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.341},
  annote =	{Keywords: approximability, unique games, linear equation, gadget, linear programming}
}
Document
DOI: 10.4230/DagRep.2.11.1
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)

Authors: Johan Hastad, Andrei Krokhin, and Dániel Marx

Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)

Abstract
During the past two decades, an impressive array of diverse methods from several different mathematical fields, including algebra, logic, analysis, probability theory, graph theory, and combinatorics, have been used to analyze both the computational complexity and approximabilty of algorithmic tasks related to the constraint satisfaction problem (CSP), as well as the applicability/limitations of algorithmic techniques. The Dagstuhl Seminar 12451 ``The Constraint Satisfaction Problem: Complexity and Approximability'' was aimed at bringing together researchers using all the different techniques in the study of the CSP, so that they can share their insights. This report documents the material presented during the course of the seminar.
Cite as

Johan Hastad, Andrei Krokhin, and Dániel Marx. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). In Dagstuhl Reports, Volume 2, Issue 11, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{hastad_et_al:DagRep.2.11.1,
  author =	{Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{Hastad, Johan and Krokhin, Andrei and Marx, D\'{a}niel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.11.1},
  URN =		{urn:nbn:de:0030-drops-39764},
  doi =		{10.4230/DagRep.2.11.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjceture; Fixed-parameter tractability; Descriptive complexity; niversal algebra; Logic; Decomposition methods}
}
Document
DOI: 10.4230/DagSemRep.338
Complexity of Boolean Functions (Dagstuhl Seminar 02121)

Authors: Johan Hastad, Matthias Krause, David A. M. Barrington, and Rüdiger Reischuk

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Johan Hastad, Matthias Krause, David A. M. Barrington, and Rüdiger Reischuk. Complexity of Boolean Functions (Dagstuhl Seminar 02121). Dagstuhl Seminar Report 338, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{hastad_et_al:DagSemRep.338,
  author =	{Hastad, Johan and Krause, Matthias and Barrington, David A. M. and Reischuk, R\"{u}diger},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 02121)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{338},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.338},
  URN =		{urn:nbn:de:0030-drops-152207},
  doi =		{10.4230/DagSemRep.338},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact